home *** CD-ROM | disk | FTP | other *** search
/ The PC-SIG Library 10 / The PC-Sig Library - Shareware for the IBM PC and Compatibles (PC-SIG)(Tenth Edition Disks 1-2804)(1991).iso / PC_SIGCD / 22 / 4 / DISK2247.ZIP / CBASE101.ZIP / BTREE101.ZIP / BTREE.H < prev    next >
Text File  |  1990-06-20  |  6KB  |  182 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /* #ident    "@(#)btree.h    1.4 - 90/06/20" */
  5.  
  6. /*man---------------------------------------------------------------------------
  7. NAME
  8.      btree - B-tree file management library
  9.  
  10. SYNOPSIS
  11.      #include <btree.h>
  12.  
  13. DESCRIPTION
  14.      The btree library consists of a set of routines for the creation
  15.      and manipulation of file-based B-tree structures.  The B+-tree
  16.      variety of B-tree is used to provide efficient sequential as well
  17.      as random access.
  18.  
  19.      btree uses the blkio library for file access and buffering.
  20.      bexit should therefore be used in place of exit.
  21.  
  22. SEE ALSO
  23.      btclose, btcreate, btcursor, btdelcur, btdelete, btfirst, btfix,
  24.      btgetcur, btgetk, btgetlck, btinsert, btkeycmp, btkeycnt,
  25.      btkeysize, btlast, btlock, btnext, btopen, btprev, btsearch,
  26.      btsetbuf, btsetcur, btsetvbuf, btsync.
  27.  
  28. ------------------------------------------------------------------------------*/
  29. #ifndef BTREE_H        /* prevent multiple includes */
  30. #define BTREE_H
  31.  
  32. #include <blkio.h>
  33. /*#include <stddef.h>*/
  34.  
  35. /* constants */
  36. #define BTOPEN_MAX    BOPEN_MAX    /* max # btrees open at once */
  37. #define BTBUFCNT    ((size_t)12)    /* default # of nodes to buffer */
  38.  
  39. /* macro to calculate buffer size needed by a btree */
  40. #define    BTBUFSIZ(M, KEYSIZE, BUFCNT) ((size_t)(                \
  41.     sizeof(bthdr_t) +                        \
  42.     (BUFCNT) * (                            \
  43.         offsetof(btnode_t, keyv) +                \
  44.         ((M) - 1) * (KEYSIZE) +                    \
  45.         (M) * sizeof(bpos_t)                    \
  46.     )                                \
  47. ))
  48.  
  49. /* type definitions */
  50. typedef struct {        /* btree position */
  51.     bpos_t node;        /* block number of node */
  52.     int key;        /* key number in node */
  53. } btpos_t;
  54.  
  55. /* pointer to field comparison function */
  56. #ifdef AC_PROTO
  57. typedef int (*btcmp_t)(const void *p1, const void *p2, size_t n);
  58. #else
  59. typedef int (*btcmp_t)();
  60. #endif
  61.  
  62. typedef struct {        /* btree node */
  63.     bpos_t lsib;        /* block number of left sibling */
  64.     bpos_t rsib;        /* block number of right sibling */
  65.     int n;            /* number keys in node  (n <= (m - 1)) */
  66.     void *keyv;        /* pointer to m keys */
  67.     bpos_t *childv;        /* pointer to (m + 1) child block numbers */
  68. } btnode_t;
  69.  
  70. typedef struct {        /* btree file header */
  71.     bpos_t flh;        /* position of free list head */
  72.     int m;            /* order of tree */
  73.     size_t keysize;        /* key size */
  74.     int flags;        /* flags */
  75.     bpos_t root;        /* position of root node */
  76.     bpos_t first;        /* position of first leaf node */
  77.     bpos_t last;        /* position of last leaf node */
  78.     unsigned long keycnt;    /* number keys currently in btree */
  79.     unsigned long height;    /* current height of btree */
  80. } bthdr_t;
  81.  
  82. typedef struct {        /* field definition */
  83.     size_t offset;        /* offset of field in key */
  84.     size_t len;        /* length of field */
  85.     btcmp_t cmp;        /* comparison function */
  86.     int flags;        /* flags */
  87. } btfield_t;
  88.  
  89. typedef struct {        /* btree control structure */
  90.     bthdr_t bthdr;        /* header record */
  91.     BLKFILE *bp;        /* block file */
  92.     int flags;        /* status flags */
  93.     int fldc;        /* number of fields */
  94.     btfield_t *fldv;    /* field definitions */
  95.     btpos_t cbtpos;        /* current btree position */
  96.     btnode_t *cbtnp;    /* current node */
  97.     btpos_t *sp;        /* search path to current position */
  98. } btree_t;
  99.  
  100. /* btfield_t bit flags */
  101. #define BT_FFLAGS    (3)        /* mask for all flags */
  102. #define BT_FASC        (1)        /* ascending order */
  103. #define BT_FDSC        (2)        /* descending order */
  104.  
  105. /* function declarations */
  106. #ifdef AC_PROTO
  107. int        btclose(btree_t *btp);
  108. int        btcreate(const char *filename, int m, size_t keysize,
  109.             int fldc, const btfield_t fldv[]);
  110. int        btdelcur(btree_t *btp);
  111. int        btdelete(btree_t *btp, const void *buf);
  112. int        btfirst(btree_t *btp);
  113. int        btfix(const char *filename, int m, size_t keysize,
  114.             int fldc, const btfield_t fldv[]);
  115. int        btgetcur(btree_t *btp, btpos_t *btposp);
  116. int        btgetk(btree_t *btp, void *buf);
  117. int        btgetlck(btree_t *btp);
  118. int        btinsert(btree_t *btp, const void *buf);
  119. int        btkeycmp(btree_t *btp, const void *buf1, const void *buf2);
  120. int        btlast(btree_t *btp);
  121. int        btlock(btree_t *btp, int ltype);
  122. int        btnext(btree_t *btp);
  123. btree_t *    btopen(const char *filename, const char *type,
  124.             int fldc, const btfield_t fldv[]);
  125. int        btprev(btree_t *btp);
  126. int        btsearch(btree_t *btp, const void *buf);
  127. int        btsetbuf(btree_t *btp, void *buf);
  128. int        btsetcur(btree_t *btp, const btpos_t *btposp);
  129. int        btsetvbuf(btree_t *btp, void *buf, size_t bufcnt);
  130. int        btsync(btree_t *btp);
  131. #else
  132. int        btclose();
  133. int        btcreate();
  134. int        btdelcur();
  135. int        btdelete();
  136. int        btfirst();
  137. int        btfix();
  138. int        btgetcur();
  139. int        btgetk();
  140. int        btgetlck();
  141. int        btinsert();
  142. int        btkeycmp();
  143. int        btlast();
  144. int        btlock();
  145. int        btnext();
  146. btree_t *    btopen();
  147. int        btprev();
  148. int        btsearch();
  149. int        btsetbuf();
  150. int        btsetcur();
  151. int        btsetvbuf();
  152. int        btsync();
  153. #endif    /* #ifdef AC_PROTO */
  154.  
  155. /* macros */
  156. #define    btcursor(BTP) ((void *)(                    \
  157.         (BTP)->cbtpos.node == NIL ? NULL : ((char *)NULL + 1)    \
  158. ))
  159. #define    btkeycnt(BTP)    ((BTP)->bthdr.keycnt)
  160. #define    btkeysize(BTP)    ((BTP)->bthdr.keysize)
  161.  
  162. /* lock types */
  163. #define BT_UNLCK    (0)    /* unlock */
  164. #define BT_RDLCK    (1)    /* read lock */
  165. #define BT_WRLCK    (2)    /* write lock */
  166. #define BT_RDLKW    (3)    /* read lock, wait */
  167. #define BT_WRLKW    (4)    /* write lock, wait */
  168.  
  169. /* error codes */
  170. #define BTEOS        (-40)        /* start of btree error code domain */
  171. #define BTEMFILE    (BTEOS - 1)    /* too many open btrees */
  172. #define BTECORRUPT    (BTEOS - 2)    /* btree is corrupt */
  173. #define BTENOPEN    (BTEOS - 3)    /* btree is not open */
  174. #define BTENBUF        (BTEOS - 4)    /* buffering is off */
  175. #define BTELOCK        (BTEOS - 5)    /* incorrect lock type */
  176. #define BTENKEY        (BTEOS - 6)    /* no key */
  177. #define BTEDUP        (BTEOS - 7)    /* duplicate key */
  178. #define BTEEOF        (BTEOS - 8)    /* past end of file */
  179. #define BTEPANIC    (BTEOS - 9)    /* internal btree error */
  180.  
  181. #endif        /* #ifndef BTREE_H */
  182.